//  跟书不太一样，双向链表
class Node {
    constructor(element) {
        this.element = element
        this.next = null
        this.prev = null // 新添加的
    }
}
class DoublyLinkedList {
    constructor() {
        this.length = 0
        this.head = null
        this.tail = null // 新添加的
    }
    append(element) {
        // 1.根据元素创建节点
        var newNode = new Node(element)

        // 2.判断列表是否为空列表
        if (this.head == null) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        }

        // 3.length+1
        this.length++
    }
    insert(position, element) {
        // 1.判断越界的问题
        if (position < 0 || position > this.length) return false

        // 2.创建新的节点
        var newNode = new Node(element)

        // 3.判断插入的位置
        if (position === 0) { // 在第一个位置插入数据
            // 判断链表是否为空
            if (this.head == null) {
                this.head = newNode
                this.tail = newNode
            } else {
                this.head.prev = newNode
                newNode.next = this.head
                this.head = newNode
            }
        } else if (position === this.length) { // 插入到最后的情况
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        } else { // 在中间位置插入数据
            // 定义属性
            var index = 0
            var current = this.head
            var previous = null

            // 查找正确的位置
            while (index++ < position) {
                previous = current
                current = current.next
            }

            // 交换节点的指向顺序
            newNode.next = current
            newNode.prev = previous
            current.prev = newNode
            previous.next = newNode
        }

        // 4.length+1
        this.length++

        return true
    }
    removeAt(position) {
        // 1.判断越界的问题
        if (position < 0 || position >= this.length) return null

        // 2.判断移除的位置
        var current = this.head
        if (position === 0) {
            if (this.length == 1) {
                this.head = null
                this.tail = null
            } else {
                this.head = this.head.next
                this.head.prev = null
            }
        } else if (position === this.length - 1) {
            current = this.tail
            this.tail = this.tail.prev
            this.tail.next = null
        } else {
            var index = 0
            var previous = null

            while (index++ < position) {
                previous = current
                current = current.next
            }

            previous.next = current.next
            current.next.prev = previous
        }

        // 3.length-1
        this.length--

        return current.element
    }
    indexOf(element) {
        // 1.定义变量保存信息
        var current = this.head
        var index = 0

        // 2.查找正确的信息
        while (current) {
            if (current.element === element) {
                return index
            }
            index++
            current = current.next
        }

        // 3.来到这个位置, 说明没有找到, 则返回-1
        return -1
    }
    remove(element) {
        var index = this.indexOf(element)
        return this.removeAt(index)
    }
    isEmpty() {
        return this.length === 0
    }
    size() {
        return this.length
    }
    forwardString() {
        var current = this.head
        var forwardStr = ""

        while (current) {
            forwardStr += "," + current.element
            current = current.next
        }

        return forwardStr.slice(1)
    }
    output() {
        let temp = this.head
        while (temp) {
            console.log(temp.element)
            temp = temp.next
        }
    }
}
var myLinkedList = new DoublyLinkedList()

myLinkedList.insert(0, 3);
myLinkedList.insert(0, 4); //头插入
myLinkedList.insert(1, 6); //中间插入
myLinkedList.insert(2, 9); //中间插入
myLinkedList.insert(3, 5); //中间插入
myLinkedList.remove(0);
myLinkedList.output();
